448E - Divisors - CodeForces Solution

#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define clr(x) vector<int>().swap(x);
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vector<int>>
#define vii vector<pii>
#define random mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnd(time(0));
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define le v * 2
#define re v * 2 + 1
#define tm (tl + tr) / 2
#define no {cout << "NO" << endl; return;}
#define yes {cout << "YES" << endl; return;}
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const ll INF=9e18;
const ll MN=-2e9;
const ll MX=1e5;
const ll MXX=2e9;
const ll SQ=6e2;
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll PP=1e6+3;
const ll P2=1299827;
const ld PI=3.141592653589793;
const ld eps=1e-11;
typedef tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
    ordered_set;

void dvs(vector<ll>& v, ll x) {
    ll pw, at;
    v = {1};
    for (ll p=2; p * p <= x; p++) if (!(x % p)) {
        pw = 1;
        at = sz(v);
        while (!(x % p)) {
            x /= p;
            pw *= p;
            for (int i=0; i<at; i++) {
               v.pb(v[i] * pw);
            }
        }
    }
    if (x > 1) {
        at = sz(v);
        for (int i=0; i<at; i++) {
           v.pb(v[i] * x);
        }
    }
    sort (all(v));
}

ll n, k;
vector<ll> v, ans;

void go(ll x, ll y) {
    if (sz(ans) >= MX) return;
    if (x == 1) {
        ans.pb(1);
        return;
    }
    if (y == 0) {
        ans.pb(x);
        return;
    }
    for (auto d:v) {
        if (d > x) break;
        if (!(x % d)) {
            go(d, y - 1);
        }
    }
}

void solve() {
    cin >> n >> k;
    if (n == 1) {
        cout << 1 << endl;
        return;
    }
    dvs(v, n);
    go(n, k);
    while (sz(ans) > MX) {
        ans.pop_back();
    }
    for (auto x:ans) cout << x << " "; cout << endl;
}

int main() {
    FAST;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

/*



*/